//#include <iostream>
//#include <string>
//using namespace std;
//int main()
//{
//    int ret = 0;
//    int n;  cin >> n;
//    string s; cin >> s;
//    for (int left = 0; left < n; left++) {
//        for (int right = left + 1; right < n; right++) {
//            for (int i = 0; right - left < 2 * i; i++) {
//                if (s[left] != '0' && s[right] != '0' && s[left + i] == s[right - i])
//                    ret++;
//                else
//                    break;
//            }
//        }
//    }
//    cout << ret << endl;
//    return 0;
//}
//class Solution {
//public:
//    int ret = 0;
//    bool dph[25];
//    bool dpv[25];
//    void fun(int m, int n, vector<int>& horizontalCut, vector<int>& verticalCut, int h, int v, int money) {
//        if (h == m && v == n) {
//            ret = min(ret, money);
//        }
//        if (money > ret) return;
//        for (int i = 0; i < m - 1; i++) {
//            if (dph[i] == false)
//            {
//                dph[i] = true;
//                fun(m, n, horizontalCut, verticalCut, h + 1, v, money + horizontalCut[i] * v);
//                dph[i] = false;
//            }
//        }
//        for (int i = 0; i < n - 1; i++) {
//            if (dpv[i] == false)
//            {
//                dpv[i] = true;
//                fun(m, n, horizontalCut, verticalCut, h, v + 1, money + verticalCut[i] * h);
//                dpv[i] = false;
//            }
//        }
//    }
//    int minimumCost(int m, int n, vector<int>& horizontalCut, vector<int>& verticalCut) {
//        ret = 1000000000;
//        for (int i = 0; i < 25; i++) dph[i] = dpv[i] = false;
//        fun(m, n, horizontalCut, verticalCut, 1, 1, 0);
//
//        // int level = 1,vertical = 1;
//        // priority_queue<int> pql,pqv;
//        // for(auto  e : horizontalCut)    pql.push(e);
//        // for(auto  e : verticalCut)      pqv.push(e);
//        // int ret = 0;
//        // int a,b;
//        // while(pql.size() || pqv.size()){
//        //     if(pql.empty()) a = 0;
//        //     else    a = pql.top() * vertical;
//        //     if(pqv.empty()) b = 0;
//        //     else   b = pqv.top() * level;
//
//        //     if(a > b){
//        //         ret += a;
//        //         level++;
//        //         pql.pop();
//        //     }else if(a == b){
//        //         if(vertical > level){
//        //             ret += b;
//        //             vertical++;
//        //             pqv.pop();
//        //         }else{
//        //             ret += a;
//        //             level++;
//        //             pql.pop();
//        //         }
//        //     }
//        //     else{
//        //         ret += b;
//        //         vertical++;
//        //         pqv.pop();
//        //     }
//        // }
//        // // if(pql.top() * vertical > pqv.top() * level){
//        // //     ret+=pql.top() * vertical;
//        // //     level++;
//
//        // // }else{
//        // //     ret+=pqv.top() * level;
//        // //     vertical++;
//        // // }
//        return ret;
//    }
//};
// 6 3 28
//bool f(int x, int y) {
//    return x > y;
//}
//class Solution {
//public:
//    priority_queue<int> pqh, pqv;
//    int ret = 0;
//    void fun(int m, int n, vector<int>& horizontalCut, vector<int>& verticalCut, int h, int v, int money) {
//        if (h == m && v == n) {
//            ret = min(ret, money);   return;
//        }
//        if (money > ret) return;
//        if (h != m) {
//            //ret+= horizontalCut[i] * v;
//            fun(m, n, horizontalCut, verticalCut, h + 1, v, money + horizontalCut[h - 1] * v);
//        }
//        if (v != n)
//        {
//            fun(m, n, horizontalCut, verticalCut, h, v + 1, money + verticalCut[v - 1] * h);
//        }
//    }
//    int minimumCost(int m, int n, vector<int>& horizontalCut, vector<int>& verticalCut) {
//        sort(horizontalCut.begin(), horizontalCut.end(),f);
//        sort(verticalCut.begin(), verticalCut.end(),f);
//        ret = 100000000;
//        fun(m, n, horizontalCut, verticalCut, 1, 1, 0);
//        return ret;
//    }
//};
//int main() {
//    vector<int> a{ 2,3,1,2,3 };
//    vector<int> b{ 2,1};
//    Solution().minimumCost(6, 3, a, b);
//}